In this paper, we propose the amphibious influence maximization (AIM) modelthat combines traditional marketing via content providers and viral marketingto consumers in social networks in a single framework. In AIM, a set of contentproviders and consumers form a bipartite network while consumers also formtheir social network, and influence propagates from the content providers toconsumers and among consumers in the social network following the independentcascade model. An advertiser needs to select a subset of seed content providersand a subset of seed consumers, such that the influence from the seed providerspassing through the seed consumers could reach a large number of consumers inthe social network in expectation. We prove that the AIM problem is NP-hard to approximate to within anyconstant factor via a reduction from Feige's k-prover proof system for 3-SAT5.We also give evidence that even when the social network graph is trivial (i.e.has no edges), a polynomial time constant factor approximation for AIM isunlikely. However, when we assume that the weighted bi-adjacency matrix thatdescribes the influence of content providers on consumers is of constant rank,a common assumption often used in recommender systems, we provide apolynomial-time algorithm that achieves approximation ratio of$(1-1/e-\epsilon)^3$ for any (polynomially small) $\epsilon > 0$. Ouralgorithmic results still hold for a more general model where cascades insocial network follow a general monotone and submodular function.
展开▼
